//
// Created by LiuYou on 2021/11/30.
//

#include <iostream>
#include <vector>
#include <iterator>


/*
 * 插入排序和冒泡排序有一些地方很相似。
 */
static void insertionSort1(std::vector<int>& arr) {
    // 这个循环的条件为什么是 arr.size()?
    // 因为插入排序的思路是: 想 0 ~ 1 上有序, 0 ~ 2 上有序, ..., 最后是 0 ~ 最后一个序列的下标位置有序(即 i < arr.size())。
    for (int i = 1; i < arr.size(); ++i) {
        // 这个循环条件为什么是 j >= 0?
        // 因为下标位置为 0, 的元素也要进行比较。
        for (int j = i - 1; j >= 0; --j) {
            if (arr[j] > arr[j + 1]) {
                std::swap( arr[j], arr[j + 1] );
            }
        }
    }
}


static void insertionSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    // 0 ~ 0 是有序的。0 ~ 0 就一个数, 就是有序的。
    // 0 ~ i 想有序。
    //
    // 第一个for循环: 我要每一步完成的目标 -> 我想要在 0 ~ 1 范围内有序;
    // 想要在 0 ~ 2 范围内有序; 想要在 0 ~ 3 范围内有序; ...; 最后我想在
    // 0 ~ n-1 范围上有序。
    for (int i = 1; i < arr.size(); ++i) {
        // j >= 0 表示 j 不越界。
        for (int j = i - 1; j >= 0; --j) {
            if (arr[j] > arr[j + 1]) {
                std::swap( arr[j], arr[j + 1] );
            }
        }
    }
}


int main(int argc, char** argv) {
    std::vector<int> arr{3, 2, 5, 4, 1};
//    std::vector<int> arr{3, -2, 325, 54, 14134, 9, 38, 33, 2, 561, 1};
    insertionSort1( arr );
    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, " " ));
    std::cout << std::endl;


    return 0;
}
